// //用哈希存储排序后的路径
// //如果排序后重复，就说明结果重复，无需记录
// class Solution {
//     vector<vector<int>> ret;
//     vector<int> path;
//     int sum = 0;
//     int _target;
//     set<vector<int>> hash;

//     void dfs(vector<int>& candidates)
//     {
//         if (sum >= _target)
//         {   
//             if (sum == _target)
//             {
//                 vector<int> tmp = path;
//                 sort(tmp.begin(), tmp.end());
//                 if (!hash.count(tmp))
//                 {
//                     ret.push_back(path);
//                     hash.insert(tmp);
//                 }
//             }
//             return;
//         }
//         for (int i = 0; i < candidates.size(); i++)
//         {
//             sum += candidates[i];
//             path.push_back(candidates[i]);
//             dfs(candidates);
//             sum -= candidates[i];
//             path.pop_back();
//         }
//     }
// public:
//     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//         _target = target;
//         dfs(candidates);
//         return ret;
//     }
// };

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int sum = 0;
    int _target;

    void dfs(vector<int>& candidates, int pos)
    {
        if (sum >= _target)
        {   
            if (sum == _target)
                ret.push_back(path);

            return;
        }
        for (int i = pos; i < candidates.size(); i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);
            dfs(candidates, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        _target = target;
        dfs(candidates, 0);
        return ret;
    }
};